1. Field of the Invention
The present invention relates to an image information coding apparatus executing a process of coding of digital image information.
2. Discussion of the Related Art
As means for coding, there are two kinds of coding methods: a fixed-length coding always resulting in a constant code amount and a variable-length coding resulting in various coding amounts depending on kinds of images. Application of the fixed-length coding is convenient in system construction because the storage capacity can be easily determined in advance. However, in many cases, the fixed-length coding is generally inferior to the variable-length coding in coding efficiency. The digital color image has enormous information amount; therefore the variable-length coding is frequently used.
The Joint Photographic Coding Expert Group (JPEG), an international standard of the static image coding method, is a typical variable-length coding method. FIG. 10 shows a construction of a coding apparatus according to the JPEG, and the following is explanation thereof. In a blocking part 1002, an inputted image 1001 is divided into blocked image informations 1003 each consisting of N.times.N pixels and then transformed into a transform coefficient 1005 in a discrete cosine transform (DCT) part 1004. The transform coefficient 1005 is quantized in a quantizing part 1006 to generate the quantized transform coefficient 1007, and coded in an entropy coding part 1008 to output a code information 1009.
Problems of the variable-length coding are as follows. The code amount cannot be constant because the characteristics of the inputted image is reflected in the coding efficiency, and besides, there are some cases where high compression ratio cannot be achieved depending on the kind of inputted image or coding parameter. Furthermore, the variable-length coding method generally has complexity in processing, and thereby it is difficult to realize high-speed processing.
The data amount of digital image of a single page is enormous: for example, about 48 MByte in a case of A4 size and 16 pixels/mm. Accordingly, the system dealing with a document including a lot of digital images requires a storing device of a large capacity. Taking the cost problem into consideration, the hard disk device (HDD) is usually employed as the storing device, but in many cases this causes a bottleneck in the whole system processing because of low processing speed in reading and writing. As means for removing the bottleneck, reduction of data amount by introducing a coding method can be considered. That is, reduction of the data amount inputted to/outputted from the HDD results in a shortened storing/reading time in the HDD. In the case of storing an image whose data amount is P MByte! per a single page in a storing device having reading/writing processing speed of V.sub.D MByte/s!, if coding is carried out with the compression ratio CR, the processing time T.sub.D s! for storing the code data is expressed as follows: EQU T.sub.D =(P/CR).multidot.(1/V.sub.D) (1)
Supposing that an average processing time of a single page image in the system is T.sub.page, the following expression (2) should be assured for removing the bottleneck: EQU T.sub.D &lt;T.sub.page ( 2)
Based on the expressions (1) and (2), it is necessary to control the compression ratio CR to satisfy the following expression (3) for removing the bottleneck: EQU CR.gtoreq.P/(V.sub.D .multidot.T.sub.max) (3)
An example of a coding amount control method controlling the compression ratio is described in "Bit-Rate Control Method for DCT Image Coding", Proceedings of the 1989 IEICE Autumn Conference D-45, which is the code amount control method for a coding system similar to the JPEG. The construction is shown in FIG. 11. In a blocking part 1102, an inputted image 1101 is divided into blocked image informations 1103 each consisting of N.times.N pixels, and in a DCT part 1104, transformed into a transform coefficient 1105. The transform coefficient 1105 is stored in a memory 1106 and then quantized in a quantizing part 1107 to generate a quantized transform coefficient 1108. The quantized transform coefficient 1108 is coded in a variable-length coding (VLC) part 1109 to generate a code amount 1110, which is inputted to a quantizing step measurement/estimation part 1111. Here, the quantizing step is one of coding parameters in this coding system. The quantizing step measurement/estimation part 1111 carries out the coding processes in the quantizing part 1107 and subsequent parts thereto using plural different quantizing step sizes and measures the code amount. Based on the measured value, a constant A and a constant B in the following expression (4) are calculated, and a quantizing step value 1112 for achieving a target code amount is estimated . EQU CL=A.multidot.log(QS)+B (4)
wherein CL is the code amount and QS is the quantizing step.
Then the estimated quantizing step value 1112 is set to the quantizing part 1107 for executing the coding processes in the quantizing part 1107 and subsequent parts thereto. The repeat of the above operations enables the estimation of high precision. The above description is the explanation for one of the conventional examples of the code amount control method.
As the system employing the code amount control method shown in the conventional example 1, a high-speed image information inputting/storing system which reads plural digital image pages from an image reading device having automatic document feeder, consecutively codes them in order, and stores them in the storing device is taken as an example. If the conventional example 1 is applied to this system, the following problems occur:
1) The method in the conventional example 1 requires a memory device for storing an image whose code amount is to be controlled, namely, one page of inputted image information until the coding process is completed. In the high-speed image information inputting/storing system, the image information writing/reading speed is extremely high, and therefore it is necessary to constitute the memory device by an expensive semiconductive memory or the like, thus causing the cost problem.
2) In the conventional example 1, the coding parameter is determined by N times of coding on a single page of inputted image information which is an object whose code amount is to be controlled. Consequently, the process time for coding of the image information to be controlled T.sub.ENC is obtained by the following expression (5) assuming that coding process velocity is V.sub.ENC MByte/s!: EQU T.sub.ENC =(P/V.sub.ENC).multidot.N (5)
In the high-speed image information inputting/storing system, it is desirable not to interrupt consecutive processing on plural pages for making the best use of high-speed reading of the image reading device. In other words, the coding process part should assure that the following expression (6) is possible wherein the process time of the image reading device for reading one page is T'.sub.page : EQU T.sub.ENC &lt;T'.sub.page ( 6)
Then the following expression (7) can be drawn out of the expressions (5) and (6): EQU N.ltoreq.(T.sub.page .multidot.V.sub.ENC)/P (7)
Accordingly, the number of times of repeating N has an upper limit value. On the other hand, lower limit value N.sub.min exists and thereby the precision in the code amount control is assured. If the upper limit value obtained by the expression (7) is less than the lower limit value N.sub.min, it is impossible to carry out the code amount control having sufficient precision.
To resolve the above-described problem 1), a method can be employed in which the image information is divided into rectangular areas each of which consists of (the number of pixels in horizontal direction .times. the number of lines of the pixel block.times.n), wherein n is a positive integral number, as shown in FIG. 12, and the code amount control is carried out per every unit of divided area. FIG. 13 is a flow chart showing process procedures according to the method.
The image to be coded is divided into the rectangular areas to the number of n times as many as the area having (the number of pixels in horizontal direction .times. the number of lines of pixel blocks), namely, block lines (Step 1201). The first one of the divided rectangular areas (that is, the divided area located at the uppermost part of the original image information) is further divided into the pixel blocks consisting of the predetermined number of pixels (Step 1202). A coding parameter B is set to an initial value (Step 1203). Here, the coding parameter B is the parameter which contributes to the amount of the code outputted from the variable-length coding part. All pixel blocks in the rectangular area are compressed into the variable-length codes by the coding parameter B (Step 1204). The amount of code outputted from the variable-length coding part is added thereto, thereby the total code amount C of the rectangular area is calculated (Step 1205). It is examined whether there is a relation indicated by the following expression TA.gtoreq.C, and (TA-C).ltoreq.Th; among the total code amount C, a predetermined target code amount TA and a predetermined threshold value Th (Step 1206). If there is no relation according to the above-mentioned expression, estimation of the value of the coding parameter B is conducted so that the total code amount C satisfies the above-mentioned expression, and the processes of step 1204 and subsequent steps are repeated (Step 1208). If the relation of the expression is found, the variable-length coding part carries out coding of the whole image information to be coded by the parameter B which is currently set (Step 1208), then it is determined whether coding of all rectangular areas in the image to be coded is completed (Step 1209), and if the coding is completed, a series of processes is completed. In the case where coding of all rectangular areas is not completed, the processes of step 1202 and subsequent steps are repeated on rectangular areas located lower to the currently processed rectangular area.
In this method, if it is supposed that n=1, the required capacity of the memory device for the image of A4 size and 16 pixels/mm is approximately 1/400-1/600 of the capacity of the memory device in the case where the image is not divided.
If the coding processing speed is not sufficiently high for the throughput of the system, the method of paralleling of the coding processes is utilized for gaining the processing speed. In the case of parallel coding processes, it is necessary to synchronize the timings of process starting, completing, and so forth. However, the coding processing time for the variable-length coding changes depending on the generated code amount; therefore the satisfying effect of speed-up owing to parallel processing usually cannot be obtained because of the overhead for synchronization. The conventional example 2 is effective to resolve the problem. In the conventional example 2, code amount control is carried out per every unit of divided area, and accordingly, if the code amount control unit and the paralleling unit are rendered equal, the coding processing speeds are approximately the same, thus reducing the overhead for synchronization. Consequently, it turns out that the code amount control per every unit of divided area such as in the conventional example 2 is effective in the speed-up of the coding process.
One of the code amount control methods for resolving the above-described problem 2 is an image data compressing method disclosed by Japanese Patent Application Laid-Open No. Hei. 3-195179 (1991), which is supposed to be the conventional example 3 of the code amount control. A flow chart showing process procedures in the conventional example 3 is shown in FIG. 14 and an example of area division and selection of representative blocks is shown in FIG. 15.
At first, the image to be coded is divided into pixel blocks each consisting of the predetermined number of pixels (Step 1401). Then the image to be coded is divided into plural areas as shown in FIG. 15 and a pixel block located at the specific position of each area is assumed to be the representative block (Step 1402). A cut-off frequency parameter F is set to an initial value (Step 1403). Here, the cut-off frequency parameter F is the parameter which contributes the amount of code outputted from the variable-length coding part. Next, DCT is carried out on the selected representative block, thereby each block is coded by the parameter F and the compression ratio of each block is obtained (Step 1404). The average value Y of the compression ratios of the representative blocks is calculated (Step 1405), and it is examined whether the average value Y of the compression ratios is close to the target compression ratio X (Step 1406). If the average value Y is close to the target compression ratio X, the coding by the cut-off frequency parameter F which is currently set is conducted on the whole image information to be coded (Step 1410), and a series of processes is completed. If the average value Y is not close to the target compression ratio X, the values Y and X are compared with each other (Step 1407). In the case where the value Y is smaller than the value X, the cut-off frequency parameter F is raised and the processes of step 1404 and the subsequent steps are repeated (Step 1408). In the case where the value Y is larger than the value X, the cut-off frequency parameter F is lowered and the processes of step 1404 and the subsequent steps are repeated (Step 1409).
Japanese Patent Application Laid-Open No. Hei. 4-87468 (1992) discloses an image data compression method which is similar to the conventional example 3 of the code amount control. The image data compression method is assumed to be a conventional example 4 of the code amount control. A flow chart showing process procedures in the conventional example 4 is shown in FIG. 16 and an example of area division and selection of representative blocks is shown in FIG. 17.
At first, the image to be coded is divided into pixel blocks each of which consists of the predetermined number of pixels (Step 1601). After division, the number of pixel blocks is M.times.N. Next, plural I columns of block lines are selected from M columns of block lines and plural J rows of block lines are selected from N rows of block lines in the image to be coded, and pixel blocks constituting those selected columns and rows are determined to be the representative blocks (Step 1602). A cut-off frequency parameter F is set to an initial value (Step 1602). Here, the cut-off frequency parameter F is the parameter which contributes to the amount of code outputted from the variable-length coding part. The selected representative blocks are coded by the cut-off frequency parameter F (Step 1604), the compression ratio of each block is calculated (Step 1605), and the average value Y of the compression ratios of the representative blocks is obtained (Step 1606). It is examined whether the average value Y of the compression ratios is close to the target compression ratio X (Step 1607). If the average value Y is close to the target compression ratio X, the whole image information to be coded is coded by the cut-off frequency parameter F which is currently set (Step 1611), and then a series of processes is completed. If the average value Y is not close to the target compression ratio X, values of Y and X are compared (Step 1608). If the value Y is smaller than X, the cut-off frequency parameter F is raised and the processes of step 1604 and subsequent steps are repeated (Step 1609). In the case where Y is larger than X, the cut-off frequency parameter F is lowered and the processes of step 1604 and subsequent steps are repeated (Step 1610).
In the conventional examples 3 and 4, if it is supposed that area division of the image is carried out so that the total data amount of the selected representative blocks is 1/M of the data amount of one page of the original image, and that coding is repeated N times in total, the coding process time T'.sub.ENC can be calculated by the following expression (8): EQU T'.sub.ENC =(P/V.sub.ENC).multidot.(1/M).multidot.(N-1)+P/V.sub.ENC( 8)
As it is clear from the expressions (5) and (8), the coding process time in the conventional examples 3 and 4, in particular, the processing time of the code amount control is reduced to 1/M of the processing time in the conventional example 1.
However, if the conventional example 2 of the code amount control is applied, the above-described problem 2) cannot be resolved because it is indispensable to carry out N times of coding process on the whole image information to be coded.
In the conventional examples 3 and 4 of the code amount control, there are no descriptions focusing on the capacity of the memory device in their patent applications, and therefore it seems that the area division of the inputted image and the coding process on the divided area unit on purpose to reduce the capacity of the memory device are not considered. However, according to the description about apparatus in these applications, there is a possibility of applying these conventional examples to the code amount control per every unit of divided area depending upon circumstances. Even if the conventional examples 3 and 4 can be applied to the code amount control per every unit of divided area, there occurs further problems.
As shown in the conventional examples 3 and 4 of the code amount control, in the method of reducing the number of blocks to be coded for shortening the processing time of the code amount control by selecting the representative blocks, the way of selection of the representative blocks has a great influence on precision of the code amount control. Consequently, if the representative blocks do not sufficiently reflect the characteristic of the original image, it is difficult to conduct the high precise prediction of the code amount.
For example, in the case where the code amount control of the conventional example 4 is applied to coding of the image information in which a picture image contains character image parts, there is a possibility of selecting many character image parts as the representative blocks as shown in FIG. 18. If such selection of the representative blocks is conducted, the ratio of the picture image and the character image in the representative blocks is different from that of the original image information, which causes fear of deterioration of precision in the code amount control. Thus, according to such systematic method of selecting the representative blocks, there is a possibility that the representative blocks may reflect the local characteristic of the original image.
In the selection of the representative blocks in the conventional examples 3 and 4, it is necessary to take two-dimensional position of the pixel block in the image information into consideration. In other words, if there is no information about two-dimensional positions of the pixel blocks, it is hard to realize the area division of the image or determination of positions of the representative blocks in the divided area in the conventional example 3, as well as the selection of the representative blocks per unit of column and row in the conventional example 4.